#!/usr/bin/env python3

from time import time

def euler82():
  """
  Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.
  """
  matrix_ori = []
  res_list = []
  with open("matrix_test.txt") as file:
    for line in file.readlines():
      matrix_ori.append(list(map(lambda x: [int(x),None,0],line.strip().split(","))))
  len_matrix = len(matrix_ori)
  for i in range(len_matrix):
    print(i)
    push_value = []
    matrix_sum = matrix_ori[:]
    push_value.append((i,1,0))

    matrix_sum[i][1][1] = matrix_sum[i][1][0] + matrix_sum[i][0][0]
    while len(push_value)!=0:
      print(push_value)
      for item in push_value[:]:
        tab=[]
        tab.append((item[0]-1,item[1],-1))
        tab.append((item[0]+1,item[1],1))
        tab.append((item[0],item[1]+1,0))
        #print(tab)
        for value in tab:
          if min(value[:-1])<0 or max(value[:-1]) >= len_matrix or (item[2]!=0 and item[2]+value[2]==0):
            continue
          if value not in push_value: push_value.append(value)
          new_value = matrix_sum[value[0]][value[1]][0] + matrix_sum[item[0]][item[1]][1]
          if matrix_sum[value[0]][value[1]][1] == None:
            matrix_sum[value[0]][value[1]][1] = new_value
          else:
            matrix_sum[value[0]][value[1]][1] = min(new_value,matrix_sum[value[0]][value[1]][1])
        push_value.remove(item)
    #print(matrix_sum)
    res_list.append(min(map(lambda x: x[-1][1],matrix_sum)))
  return min(res_list)


          
    
"""
Print answer and process time
"""
if __name__=="__main__":
  time_begin = time()
  print("Answer : {}".format(euler82()))
  print("Time : {}\"".format(time()-time_begin))
